/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/asteroid-collision
   @Language: C++
   @Datetime: 19-05-15 09:42
   */

class Solution {
public:
	/**
	 * @param asteroids: a list of integers
	 * @return: return a list of integers
	 */
	vector<int> asteroidCollision(vector<int> &asteroids) {
		// write your code here
		vector<int> v;
		for(const int &a:asteroids){
			if(a>=0){
				v.push_back(a);
				continue;
			}
			bool eat=false;
			for(; !eat && v.size();){
				int top=v.back();
				if(top<0){
					eat=true;
					v.push_back(a);
				}
				else if(top==-a) {
					eat=true;
					v.pop_back();
				}
				else if(top>-a){
					eat=true;
				}
				else v.pop_back();
			}
			if(!eat) v.push_back(a);
		}
		return v;
	}
};
